/*
棋盘中有一个特殊方格，用L型骨牌覆盖其余格子
*/
#include<iostream>
using namespace std;
#define MAX 1025

int board[MAX][MAX];	 // 表示棋盘，MAX为常量
int tile = 1; // L型骨牌的编号,从1开始

// (tr, tc)表示棋盘左上角位置，(dr, dc)表示特殊方格位置，k表示棋盘大小2^k
void ChessBoard1(int tr,int tc,int dr,int dc,int k)
{
	// 递归出口
	if(k==0) return;
	
	// 取一个L型骨，其牌号为tile
	int t = tile++;
	
	// 分割的子棋盘大小 
	int size = 1<<(k-1);

	// 特殊方格在左上角象限中
	if(dr<tr+size && dc<tc+size)	
		ChessBoard1(tr, tc, dr, dc, k-1); // 继续分割左上角象限
	
	// 特殊方格不在左上角象限中
	else
	{
		// 用t号L型骨牌覆盖左上角象限的右下角
		board[tr+size-1][tc+size-1] = t;
		
		// 继续分割左上角象限
		ChessBoard1(tr, tc, tr+size-1, tc+size-1, k-1);
	}
	
	// 特殊方格在右上角象限中
	if(dr<tr+size && dc>=tc+size)
		ChessBoard1(tr,tc+size,dr,dc,size);
	
	// 特殊方格不在右上角象限中
	else
	{
		// 用t号L型骨牌覆盖右上角象限的左下角
		board[tr+size-1][tc+size] = t;
		
		// 继续分割右上角象限
		ChessBoard1(tr, tc+size, tr+size-1, tc+size, k-1);
	}
	
	// 特殊方格在左下角象限中
	if(dr>=tr+size && dc<tc+size)
		ChessBoard1(tr+size,tc,dr,dc,k-1); // 继续分割左下角象限
	
	// 特殊方格不在左下角象限中
	else
	{
		// 用t号L型骨牌覆盖左下角象限的右上角
		board[tr+size][tc+size-1] = t;
		
		// 继续分割左下角象限
		ChessBoard1(tr+size, tc, tr+size, tc+size-1, k-1);
	}
	
	// 特殊方格在右下角象限中
	if(dr>=tr+size && dc>=tc+size)
		ChessBoard1(tr+size,tc+size,dr,dc,k-1); // 继续分割右下角象限
	
	// 特殊方格在右下角象限中
	else
	{
		// 用t号L型骨牌覆盖右下角象限的左上角
		board[tr+size][tc+size] = t;
		
		// 继续分割右下角象限
		ChessBoard1(tr+size, tc+size, tr+size, tc+size, k-1);
	}
}

// 递归算法，求2^k*2^k棋盘的覆盖问题 
void ChessBoard(int dr,int dc,int k)	
{
	ChessBoard1(0, 0, dr, dc, k);
}

int main()
{
	// 表示棋盘大小为2^k*2^k 
	int k = 3;
	int size = 1<<k ;
	
	// 特殊方格的位置
	int dr=1, dc=2;
	
	// 棋盘覆盖问题
	ChessBoard(dr, dc, k);
	
	// 输出方案
	for(int i=0; i<size; i++)
	{
		for(int j=0; j<size; j++)
			printf("%4d",board[i][j]);
		printf("\n");
	}
	return 0;
}
